#include<bits/stdc++.h>
using namespace std;
const int N = 12;
const int MOD = 1e9+7;
struct node{
    int x1,x2,y1,y2,lmt;
    friend bool operator<(node va,node vb){
        return va.y2 < vb.y2;
    }
} nds[N];
int qpow(int x,int p){
    int res = 1;
    while(p){
        if(p & 1){
            res = 1ll*res*x%MOD;
        }
        x = 1ll*x*x%MOD;
        p >>= 1;
    }
    return res;
}
int nums[N*4],ncnt;
int mat[N*4][N*4];
void solve(){
    ncnt = 0;
    int h,w,m,n;
    cin>>h>>w>>m>>n;
    nums[++ncnt] = h + 1;
    nums[++ncnt] = 1;
    for(int i = 1;i <= n;i++){
        cin>>nds[i].x1>>nds[i].y1>>nds[i].x2>>nds[i].y2>>nds[i].lmt;
        nums[++ncnt] = nds[i].y1;
        nums[++ncnt] = nds[i].y2 + 1;
        nums[++ncnt] = nds[i].x1;
        nums[++ncnt] = nds[i].x2 + 1;
    }
    sort(nums + 1,nums + 1 + ncnt);
    int rows = unique(nums + 1,nums + 1 + ncnt) - nums - 1;
    for(int i = 1;i <= n;i++){
        nds[i].y1 = lower_bound(nums + 1,nums + 1 + rows,nds[i].y1) - nums;
        nds[i].y2 = lower_bound(nums + 1,nums + 1 + rows,nds[i].y2 + 1) - nums;
        nds[i].x1 = lower_bound(nums + 1,nums + 1 + rows,nds[i].x1) - nums;
        nds[i].x2 = lower_bound(nums + 1,nums + 1 + rows,nds[i].x2 + 1) - nums;
    }
    int ans = 0;
    for(int S = 0;S < (1<<n);S++){
        for(int i = 1;i < rows;i++){
            for(int j = 1;j < rows;j++){
                mat[i][j] = m;
            }
        }
        for(int i = 1;i<=n;i++)
        {
            int lmt = nds[i].lmt;
            if((S>>(i - 1))&1){
                lmt--;
            }
            for(int x = nds[i].x1;x < nds[i].x2;x++){
                for(int y = nds[i].y1;y < nds[i].y2;y++){
                    mat[x][y] = min(mat[x][y],lmt);
                }
            }            
        }
        int res = 1;
        for(int i = 1;i < rows;i++){
            for(int j = 1;j < rows;j++){
                res = 1ll*res*qpow(mat[i][j],(nums[i + 1] - nums[i])*(nums[j + 1] - nums[j]))%MOD;
            }
        }
        int cnt = __builtin_popcount(S);
        if(cnt&1){
            ans = (ans - res + MOD)%MOD;
        }else{
            ans = (ans + res)%MOD;
        }
    }
    cout<<ans<<'\n';
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}